package com.cr4y0n.hot100;

/**
 * @author cr4y0n
 * <a href="https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked">和为 K 的子数组</a>
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 * 子数组是数组中元素的连续非空序列。
 * 示例 1：
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 * 示例 2：
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 */
public class _560_SubarraySumEqualsK {
    static class Solution {
        public int subarraySum(int[] nums, int k) {
            int[] pre = new int[nums.length];
            int count = 0;
            pre[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                pre[i] = pre[i - 1] + nums[i];
            }
            for (int i = 0; i < nums.length; i++) {
                if (pre[i] == k) {
                    count++;
                }
            }
            for (int i = nums.length - 1; i > 0; i--) {
                for (int j = 0; j < i; j++) {
                    if (pre[i] - pre[j] == k) {
                        count++;
                    }
                }
            }
            return count;
        }
    }
}
